package com.zq.solution;

/**
 * @ClassName Pow
 * @Description 求一个数的乘方
 *算法说明： 根据 (X^a)^b = X^(a*b)
 * 　　如果如果求2的8次方，我们可以先假定2^2=a,于是2^8 = （2^2）^4 ，那么就是a^4 ；
 *    假定 a^2 = b，那么 a^4 = b^2，而b^2可以写成(b^2)^1。于是现在2^8就转换成：b*b
 * 　　也就是说我们将乘方的运算转换为乘法的运算。
 * 　　求x^y的值，当y是偶数的时候，最后能转换成两个数相乘，当时当y是奇数的时候，最后我们必须要在返回值后面额外的乘以一个x。
 * @Author ZQ
 * @Date 2020/11/5 14:10
 * @Version V1.0
 **/
public class Pow {
    public static int pow(int x , int y){
        if(x == 0 || x == 1) return x;
        if(y > 1){
            int b = y/2;
            int a = x*x;
            if(y%2 == 1) return pow(a,b)*x;
            else return pow(a,b);
        }else if(y == 0) return 1;
        else  return x;
    }

    public static void main(String[] args) {
        System.out.println(pow(2,5));
    }
}
